Matrix analytic method
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
top
In probability theory, the matrix analytic method is a technique to compute the stationary probability distribution of a Markov chain which has a repeating structure (after some point) and a state space which grows unboundedly in no more than one dimension.cite-ref-1[1]cite-ref-2[2] Such models are often described as M/G/1 type Markov chains because they can describe transitions in an M/G/1 queue.cite-ref-meini-3-0[3]cite-ref-4[4] The method is a more complicated version of the matrix geometric method and is the classical solution method for M/G/1 chains.cite-ref-5[5]
Contents
• Tools
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
Method description
An M/G/1-type stochastic matrix is one of the formcite-ref-meini-3-1[3]
P = ( B 0 B 1 B 2 B 3 ⋯ ⋯ A 0 A 1 A 2 A 3 ⋯ ⋯ A 0 A 1 A 2 ⋯ ⋯ A 0 A 1 ⋯ ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋱ ) {\displaystyle P={\begin{pmatrix}B_{0}&B_{1}&B_{2}&B_{3}&\cdots \\A_{0}&A_{1}&A_{2}&A_{3}&\cdots \\&A_{0}&A_{1}&A_{2}&\cdots \\&&A_{0}&A_{1}&\cdots \\\vdots &\vdots &\vdots &\vdots &\ddots \end{pmatrix}}}
where Bi and Ai are k × k matrices. (Note that unmarked matrix entries represent zeroes.) Such a matrix describes the embedded Markov chain in an M/G/1 queue.cite-ref-6[6]cite-ref-7[7] If P is irreducible and positive recurrent then the stationary distribution is given by the solution to the equationscite-ref-meini-3-2[3]
P π π = π π and e T π π = 1 {\displaystyle P\pi =\pi \quad {\text{ and }}\quad \mathbf {e} ^{\text{T}}\pi =1}
where e represents a vector of suitable dimension with all values equal to 1. Matching the structure of P, π is partitioned to π1, π2, π3, …. To compute these probabilities the column stochastic matrix G is computed such thatcite-ref-meini-3-3[3]
G = ∑ ∑ i = 0 ∞ ∞ G i A i . {\displaystyle G=\sum _{i=0}^{\infty }G^{i}A_{i}.}
A ¯ ¯ i + 1 = ∑ ∑ j = i + 1 ∞ ∞ G j − − i − − 1 A j B ¯ ¯ i = ∑ ∑ j = i ∞ ∞ G j − − i B j {\displaystyle {\begin{aligned}{\overline {A}}_{i+1}&=\sum _{j=i+1}^{\infty }G^{j-i-1}A_{j}\\{\overline {B}}_{i}&=\sum _{j=i}^{\infty }G^{j-i}B_{j}\end{aligned}}}
then π0 is found by solvingcite-ref-meini-3-5[3]
B ¯ ¯ 0 π π 0 = π π 0 ( e T + e T ( I − − ∑ ∑ i = 1 ∞ ∞ A ¯ ¯ i ) − − 1 ∑ ∑ i = 1 ∞ ∞ B ¯ ¯ i ) π π 0 = 1 {\displaystyle {\begin{aligned}{\overline {B}}_{0}\pi _{0}&=\pi _{0}\\\quad \left(\mathbf {e} ^{\text{T}}+\mathbf {e} ^{\text{T}}\left(I-\sum _{i=1}^{\infty }{\overline {A}}_{i}\right)^{-1}\sum _{i=1}^{\infty }{\overline {B}}_{i}\right)\pi _{0}&=1\end{aligned}}}
π π i = ( I − − A ¯ ¯ 1 ) − − 1 [ B ¯ ¯ i + 1 π π 0 + ∑ ∑ j = 1 i − − 1 A ¯ ¯ i + 1 − − j π π j ] , i ≥ ≥ 1. {\displaystyle \pi _{i}=(I-{\overline {A}}_{1})^{-1}\left[{\overline {B}}_{i+1}\pi _{0}+\sum _{j=1}^{i-1}{\overline {A}}_{i+1-j}\pi _{j}\right],i\geq 1.}
Computation of G
• functional iterations
Tools
References
cite-note-11. ↑ citerefharchol-balter2012Harchol-Balter, M. (2012). "Phase-Type Distributions and Matrix-Analytic Methods". Performance Modeling and Design of Computer Systems. pp. 359–379. doi:10.1017/CBO9781139226424.028. ISBN 9781139226424.
cite-note-44. ↑ citerefstathopoulosriskahuasmirni2005Stathopoulos, A.; Riska, A.; Hua, Z.; Smirni, E. (2005). "Bridging ETAQA and Ramaswami's formula for the solution of M/G/1-type processes". Performance Evaluation. 62 (1–4): 331–348. CiteSeerX 10.1.1.80.9473. doi:10.1016/j.peva.2005.07.003.
cite-note-55. ↑ citerefriskasmirni2002Riska, A.; Smirni, E. (2002). "M/G/1-Type Markov Processes: A Tutorial" (PDF). Performance Evaluation of Complex Systems: Techniques and Tools. Lecture Notes in Computer Science. Vol. 2459. pp. 36. doi:10.1007/3-540-45798-4_3. ISBN 978-3-540-44252-3.
cite-note-66. ↑ citerefbolchgreinerde-meershridharbhai-trivedi2006Bolch, Gunter; Greiner, Stefan; de Meer, Hermann; Shridharbhai Trivedi, Kishor (2006). Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications (2 ed.). John Wiley & Sons, Inc. p. 250. ISBN 978-0471565253.
cite-note-88. ↑ citerefriskasmirni2002Riska, A.; Smirni, E. (2002). "Exact aggregate solutions for M/G/1-type Markov processes". ACM SIGMETRICS Performance Evaluation Review. 30: 86. CiteSeerX 10.1.1.109.2225. doi:10.1145/511399.511346.
cite-note-1212. ↑ citerefriskasmirni2002Riska, A.; Smirni, E. (2002). "MAMSolver: A Matrix Analytic Methods Tool". Computer Performance Evaluation: Modelling Techniques and Tools. Lecture Notes in Computer Science. Vol. 2324. p. 205. CiteSeerX 10.1.1.146.2080. doi:10.1007/3-540-46029-2_14. ISBN 978-3-540-43539-6.